package com.wxg.algorithm.chapter03.comparable;

import com.wxg.algorithm.chapter02.comparable.InsertionSortV2;
import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

import java.util.Random;

public class QuickSortV3<T extends Comparable> implements ISort<T> {

    public static final Random RAND = new Random();

    private InsertionSortV2 insertionSortV2;

    public QuickSortV3() {
        insertionSortV2 = new InsertionSortV2<T>();
    }

    @Override
    public void sort(T[] arr) {
        quickSort(arr, 0, arr.length-1);
    }

    /**
     * 对 arr[l...r]部分进行快速排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private void quickSort(T[] arr, int l, int r) {
        // 优化, 当元素数量较少时,切换为使用"插入排序"
        if(r - l <= 15){
            insertionSortV2.sort(arr, l, r);
            return;
        }

        int p = partition(arr, l, r);
        quickSort(arr, l, p-1);
        quickSort(arr, p+1, r);
    }

    /**
     * 对 arr[l...r] 部分进行 partition 操作
     * 返回p, 使得 arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private int partition(T[] arr, int l, int r) {

        int _targetIndex = RAND.nextInt(r-l+1) + l;

        T _temp = arr[l];
        arr[l] = arr[_targetIndex];
        arr[_targetIndex] = _temp;


        T v = arr[l];

        // arr[l+1...j] < v ; arr[j+1...i) > v
        int j = l;
        for(int i = l + 1; i <= r; i++){
            if( arr[i].compareTo(v) < 0 ){
                T temp = arr[j+1];
                arr[j+1] = arr[i];
                arr[i] = temp;
                j++;
            }
        }

        T temp = arr[l];
        arr[l] = arr[j];
        arr[j] = temp;

        return j;
    }

    public static void main(String[] args) {
        QuickSortV3<Integer> qs = new QuickSortV3<>();
        MergeSortV2<Integer> ms = new MergeSortV2<>();

        int n = 100000; // 这里不能设置过大, 否则会出现内存溢出的情况。
        Integer[] intArr = SortTestHelper.generateRandomArray(n, 0, n);
        Integer[] intArr02 = SortTestHelper.copyIntArray(intArr);

        SortTestHelper.testSort(qs, intArr);
        SortTestHelper.testSort(ms, intArr02);

        System.out.println("=== 分隔线 ===");
        System.out.println("当优化后(随机选择一个元素), 对 - 近乎有序的数组的排序 - 快速排序 - 表现很优秀了");

        Integer[] intArr03 = SortTestHelper.generateNearlyOrderedArray(n, 100);
        Integer[] intArr04 = SortTestHelper.copyIntArray(intArr03);

        SortTestHelper.testSort(qs, intArr03);
        SortTestHelper.testSort(ms, intArr04);


    }
}
